<!DOCTYPE html>
<html lang="zh">
    <head>
  <!-- 元数据 -->
  <meta charset="utf-8">
  
  
  <title>数据结构笔记 | 舛羽的笔记小站</title>
  <meta name="author" content="cy" />
  <meta http-equiv="Cache-Control" content="no-transform" />
  <meta http-equiv="Cache-Control" content="no-siteapp" />
  <meta http-equiv="X-UA-Compatible" content="IE=edge" />
  <meta name="robots" content="index,follow" />
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1" />
  <meta name="format-detection" content="telphone=no, email=no" />
  
    <meta name="keywords" content="数据结构, 算法" />
  
  <meta name="description" content="本笔记是我大一的时候自学数据结构所总结的笔记。内容不多，深度也比较低，想对数据结构进行精进的大可不必看这个，如果只是为了应付学校的考试或者入个门，这个倒是足够了。">
<meta property="og:type" content="article">
<meta property="og:title" content="数据结构笔记">
<meta property="og:url" content="http://example.com/2022/12/25/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AC%94%E8%AE%B0/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AC%94%E8%AE%B0/index.html">
<meta property="og:site_name" content="舛羽的笔记小站">
<meta property="og:description" content="本笔记是我大一的时候自学数据结构所总结的笔记。内容不多，深度也比较低，想对数据结构进行精进的大可不必看这个，如果只是为了应付学校的考试或者入个门，这个倒是足够了。">
<meta property="og:locale">
<meta property="og:image" content="https://s2.loli.net/2022/06/20/8cCSOwyQMHGrBfD.png">
<meta property="og:image" content="https://s2.loli.net/2022/06/20/lnSqshHzXMD3pKV.png">
<meta property="og:image" content="https://s2.loli.net/2022/06/20/zRNoyj5C8SaEdVP.png">
<meta property="og:image" content="https://s2.loli.net/2022/06/20/VzPNJ2ArH4iSdqD.png">
<meta property="og:image" content="https://s2.loli.net/2022/06/20/VzPNJ2ArH4iSdqD.png">
<meta property="og:image" content="https://s2.loli.net/2022/01/10/syzpeZQOdlaIYRg.jpg">
<meta property="og:image" content="https://s2.loli.net/2022/01/10/jdohleCOLcy4VTD.jpg">
<meta property="og:image" content="https://s2.loli.net/2022/06/20/6jpkPCs1vG549Ni.png">
<meta property="og:image" content="https://s2.loli.net/2022/10/19/Y8CAuiJp4axBZW1.png">
<meta property="og:image" content="https://s2.loli.net/2022/10/19/fSTzdZxqMFkyD2p.png">
<meta property="og:image" content="https://s2.loli.net/2022/10/19/o9fIQeOcGyCHWu2.png">
<meta property="article:published_time" content="2022-12-25T06:19:47.000Z">
<meta property="article:modified_time" content="2022-12-25T09:44:39.422Z">
<meta property="article:author" content="cy">
<meta property="article:tag" content="数据结构">
<meta property="article:tag" content="算法">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://s2.loli.net/2022/06/20/8cCSOwyQMHGrBfD.png">
  
  <!-- 站点验证相关 -->
  
    
    
    
  
  <!-- 样式表文件 -->
  <link rel="stylesheet" id="kratos-css" href="/css/kratosr.min.css" media="all"></script>
  
    <link rel="stylesheet" id="darkmode-css" href="/css/kr-color-dark.min.css" media="(prefers-color-scheme: dark)"></script>
    <script src="/js/kr-dark.min.js"></script>
  
  
    <link rel="stylesheet" id="highlight-css" href="/css/highlight/night-eighties.min.css" media="all"></script>
  
  
  <link rel="stylesheet" id="fontawe-css" href="/vendors/font-awesome@4.7.0/css/font-awesome.min.css" media="all"></script>
  <link rel="stylesheet" id="nprogress-css" href="/vendors/nprogress@0.2.0/nprogress.css" media="all"></script>
  
  
  
    <link rel="stylesheet" href="/vendors/@fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.css"></script>
  
  <!-- 不得不预先加载的一些JS文件 -->
  <script src="/vendors/jquery@3.6.0/dist/jquery.min.js"></script>
  
    <script src="/vendors/qrcode_js@1.0.0/qrcode.min.js"></script>
  
  
  <style>
    
      .kratos-cover.kratos-cover-2 {
        background-image: url('/images/banner.webp');
      }
    
    
      @media(min-width:768px) {
        body.custom-background {
          background-image: url('/images/bg.webp');
        }
      }
    
  </style>
  
<meta name="generator" content="Hexo 7.3.0"></head>


    <body class="custom-background">
        <div id="kratos-wrapper">
    <div id="kratos-page">
        <div id="kratos-header">
            <header id="kratos-desktop-topnav" class="kratos-topnav">
                <div class="container">
                    <div class="nav-header">
                        <nav id="kratos-menu-wrap">
                            <ul id="kratos-primary-menu" class="sf-menu">
                                
                                    
                                    
                                
                            </ul>
                        </nav>
                    </div>
                </div>
            </header>
            <header id="kratos-mobile-topnav" class="kratos-topnav">
                <div class="container">
                    <div class="color-logo"><a href="/">舛羽的笔记小站</a></div>
                    <div class="nav-toggle">
                        <a class="kratos-nav-toggle js-kratos-nav-toggle">
                            <i></i>
                        </a>
                    </div>
                </div>
            </header>
        </div>
        <div class="kratos-start kratos-hero-2">
            <!-- <div class="kratos-overlay"></div> -->
            <div class="kratos-cover kratos-cover-2 text-center">
                <div class="desc desc2 animate-box">
                    <a href="/">
                        <h2>舛羽的笔记小站</h2> <br />
                        <span></span>
                    </a>
                </div>
            </div>
        </div>

        <div id="kratos-blog-post">
            <div class="container">
                <div id="main" class="row">
                    

        

            <section class="col-md-8">

        

            <article itemscope itemtype="https://schema.org/Article">
    
    <link itemprop="mainEntityOfPage" href="http://example.com/2022/12/25/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AC%94%E8%AE%B0/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AC%94%E8%AE%B0/">
    <div class="kratos-hentry kratos-post-inner clearfix">
        <header class="kratos-entry-header">
            
                <h1 class="kratos-entry-title text-center" itemprop="name headline">数据结构笔记</h1>
            
            
            <ul class="kratos-post-meta text-center">
                <li><time datetime="2022-12-25T06:19:47.000Z" itemprop="datePublished"><i class="fa fa-calendar"></i> 2022-12-25</time></li>
                <li itemprop="author" itemscope itemtype="https://schema.org/Person">
                    <i class="fa fa-user"></i> 作者 <span itemprop="name">cy</span>
                </li>
                <li>
                    <i class="fa fa-edit"></i> 
                    
                    
                        ~9.37K
                    
                    字
                </li>
                
            </ul>
        </header>
        <div class="kratos-post-content">
            
            <div id="expire-alert" class="alert alert-warning hidden" role="alert">
                <div class="icon"><i class="fa fa-warning"></i></div>
                <div class="text"><p>本文最后编辑于 <time datetime="1671961479422"></time> 前，其中的内容可能需要更新。</p></div>
            </div>
            
            
            
            <hr />
            <div itemprop="articleBody"><p>本笔记是我大一的时候自学数据结构所总结的笔记。内容不多，深度也比较低，想对数据结构进行精进的大可不必看这个，如果只是为了应付学校的考试或者入个门，这个倒是足够了。</p>
<span id="more"></span>
<p>当时也是刚接触到md，所以有些地方写的不太好，请谅解</p>
<h2 id="第一章：数据结构绪论"><a href="#第一章：数据结构绪论" class="headerlink" title="第一章：数据结构绪论"></a>第一章：数据结构绪论</h2><h3 id="逻辑结构与物理结构"><a href="#逻辑结构与物理结构" class="headerlink" title="逻辑结构与物理结构"></a>逻辑结构与物理结构</h3><h4 id="逻辑结构"><a href="#逻辑结构" class="headerlink" title="逻辑结构"></a>逻辑结构</h4><p>逻辑结构：是指<strong>数据对象</strong>中<strong>数据元素之间</strong>的相互关系面向问题的。</p>
<p>逻辑结构可以分为四类。</p>
<h5 id="集合结构"><a href="#集合结构" class="headerlink" title="集合结构"></a>集合结构</h5><p>即数据除了在同一集合中无其他关系。</p>
<p><img src="https://s2.loli.net/2022/06/20/8cCSOwyQMHGrBfD.png" alt=""></p>
<h5 id="线性结构"><a href="#线性结构" class="headerlink" title="线性结构"></a>线性结构</h5><p>数据元素<strong>之间</strong>是<strong>一对一</strong>关系</p>
<p><img src="https://s2.loli.net/2022/06/20/lnSqshHzXMD3pKV.png" alt=""></p>
<h5 id="树形结构"><a href="#树形结构" class="headerlink" title="树形结构"></a>树形结构</h5><p>数据元素之<strong>间</strong>呈现<strong>一对多关系</strong></p>
<p><img src="https://s2.loli.net/2022/06/20/zRNoyj5C8SaEdVP.png" alt=""></p>
<h5 id="图形结构"><a href="#图形结构" class="headerlink" title="图形结构"></a>图形结构</h5><p>数据元素之间呈现<strong>多对多</strong>关系</p>
<p><img src="https://s2.loli.net/2022/06/20/VzPNJ2ArH4iSdqD.png" alt=""></p>
<h4 id="物理结构"><a href="#物理结构" class="headerlink" title="物理结构"></a>物理结构</h4><h5 id="线性存储"><a href="#线性存储" class="headerlink" title="线性存储"></a>线性存储</h5><p>数据均放在连续的存储空间中。可以进行随机访问。链式存储</p>
<h5 id="链式存储"><a href="#链式存储" class="headerlink" title="链式存储"></a>链式存储</h5><p>把数据存储在任意存储单元，各个数据的关系通过指针来表示</p>
<h2 id="第二章：算法"><a href="#第二章：算法" class="headerlink" title="第二章：算法"></a>第二章：算法</h2><h3 id="概念"><a href="#概念" class="headerlink" title="概念"></a>概念</h3><p>说白了就是解决问题办法</p>
<h3 id="特性"><a href="#特性" class="headerlink" title="特性"></a>特性</h3><h4 id="基本的输入输出"><a href="#基本的输入输出" class="headerlink" title="基本的输入输出"></a>基本的输入输出</h4><h4 id="有穷性"><a href="#有穷性" class="headerlink" title="有穷性"></a>有穷性</h4><p>指算法在执行有限的步骤之后，自动结束而不会出现无线循环，并且每一个步骤在可接受范围内完成</p>
<h4 id="确定性"><a href="#确定性" class="headerlink" title="确定性"></a>确定性</h4><p>算法每一步都具有确定的定义，不能同一种情况进入不同的分支</p>
<h4 id="可行性"><a href="#可行性" class="headerlink" title="可行性"></a>可行性</h4><p>算法的每一步都必须可行</p>
<h3 id="设计要求"><a href="#设计要求" class="headerlink" title="设计要求"></a>设计要求</h3><h4 id="正确性"><a href="#正确性" class="headerlink" title="正确性"></a>正确性</h4><p>算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性，能正确反应问题的需求、能够的到问题的正确答案</p>
<font color='red'>本人翻译：就是算法算出来的必须是对的</font>

<h4 id="健壮性"><a href="#健壮性" class="headerlink" title="健壮性"></a>健壮性</h4><p>当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名奇妙的结果</p>
<font color='red'>本人翻译：就是当用户点一份蛋炒饭时程序不会炸</font>

<h4 id="可读性"><a href="#可读性" class="headerlink" title="可读性"></a>可读性</h4><p>算法设计的另一目的是为了便于月的、理解和交流</p>
<font color='red'>本人翻译：说白了就是要让人能看懂</font>

<h4 id="时间效率高和存储量低"><a href="#时间效率高和存储量低" class="headerlink" title="时间效率高和存储量低"></a>时间效率高和存储量低</h4><font color='red'>本人翻译：跑程序时电脑不卡，跑的快，又不占内存</font>

<h3 id="算法优劣的判断方法"><a href="#算法优劣的判断方法" class="headerlink" title="算法优劣的判断方法"></a>算法优劣的判断方法</h3><h4 id="时间复杂度"><a href="#时间复杂度" class="headerlink" title="时间复杂度"></a>时间复杂度</h4><p> 时间复杂度所需消耗的时间<strong>即基本操作执行次数</strong></p>
<h5 id="时间复杂度的计算"><a href="#时间复杂度的计算" class="headerlink" title="时间复杂度的计算"></a>时间复杂度的计算</h5><p>该方法就是大O阶表示法的计算方法</p>
<p>（1）用<strong>常数 1</strong>取代<strong>运行时间中的</strong>所有加法常数</p>
<p>（2）在修改后的运行次数函数中，<strong>只保留最高阶项</strong></p>
<p>（3）如果最高阶项<strong>存在且不是 1</strong>，<strong>则去除与这个项相乘的常数</strong></p>
<h5 id="常用时间复杂度的比较"><a href="#常用时间复杂度的比较" class="headerlink" title="常用时间复杂度的比较"></a>常用时间复杂度的比较</h5><p><img src="https://s2.loli.net/2022/06/20/VzPNJ2ArH4iSdqD.png" alt=""></p>
<h4 id="空间复杂度"><a href="#空间复杂度" class="headerlink" title="空间复杂度"></a>空间复杂度</h4><p>运行完一个程序<strong>所需内存的大小</strong></p>
<font color='red'>注：感觉用得不多，目前了解定义就行</font>

<h2 id="第三章：线性表"><a href="#第三章：线性表" class="headerlink" title="第三章：线性表"></a>第三章：线性表</h2><h3 id="定义"><a href="#定义" class="headerlink" title="定义"></a>定义</h3><p>零个或多个数据元素的<strong>有限序列</strong></p>
<h3 id="线性表的顺序存储结构"><a href="#线性表的顺序存储结构" class="headerlink" title="线性表的顺序存储结构"></a>线性表的顺序存储结构</h3><h4 id="定义-1"><a href="#定义-1" class="headerlink" title="定义"></a>定义</h4><p>用一段连续得存储空间对数据进行存储</p>
<font color='red'>本人翻译：说白了就是数组</font>

<h4 id="特性-1"><a href="#特性-1" class="headerlink" title="特性"></a>特性</h4><p>拥有随机访问特性</p>
<h4 id="时间复杂度-1"><a href="#时间复杂度-1" class="headerlink" title="时间复杂度"></a>时间复杂度</h4><p>(1)对于存取操作</p>
<p>线性表的顺序存储结构，对于<strong>存取操作</strong>，其<strong>时间复杂度</strong>为O(1)</p>
<p>因为<strong>元素位置</strong>可以<strong>直接计算得到</strong></p>
<p> (2)对于<strong>插入和删除</strong>操作</p>
<p>对于<strong>插入和删除</strong>操作，其<strong>时间复杂度</strong>为O(n)因为插入或删除后，需要<strong>移动其余元素</strong></p>
<h4 id="使用场景"><a href="#使用场景" class="headerlink" title="使用场景"></a>使用场景</h4><p>因此，线性表顺序存储结构<strong>比较适用于</strong>元素<strong>存取操作较多</strong>，<strong>增删操作较少</strong>的场景</p>
<h3 id="线性表的链式存储结构"><a href="#线性表的链式存储结构" class="headerlink" title="线性表的链式存储结构"></a>线性表的链式存储结构</h3><h4 id="定义-2"><a href="#定义-2" class="headerlink" title="定义"></a>定义</h4><p><strong>一个或多个结点组合而成的</strong>数据结构称为链表</p>
<h4 id="结点"><a href="#结点" class="headerlink" title="结点"></a>结点</h4><p>结点一般由两部分组成</p>
<h5 id="数据域"><a href="#数据域" class="headerlink" title="数据域"></a>数据域</h5><p>用来装需要存储的数据</p>
<h5 id="指针域"><a href="#指针域" class="headerlink" title="指针域"></a>指针域</h5><p>存储指向下一个结点的指针</p>
<h5 id="头结点"><a href="#头结点" class="headerlink" title="头结点"></a>头结点</h5><p>为了能更加方便地对链表进行操作，会在<strong>单链表的第一个结点（即头指针）前</strong>附<strong>设一个结点</strong>，称为 <strong>头结点</strong></p>
<p>该结点不装任何实际数据方便操作</p>
<font color='red'>注：并非每个链表都有</font>

<h5 id="头指针"><a href="#头指针" class="headerlink" title="头指针"></a>头指针</h5><p>指向第一个结点的指针称之为头指针</p>
<font color='red'>注：不一定是头指针</font>

<h3 id="单链表"><a href="#单链表" class="headerlink" title="单链表"></a>单链表</h3><h4 id="单链表的时间复杂度"><a href="#单链表的时间复杂度" class="headerlink" title="单链表的时间复杂度"></a>单链表的时间复杂度</h4><p>（1）存取操作</p>
<p>而对于单链表结构，假设需要获取第 i 个元素，则必须从第一个结点开始依次进行遍历，直到达到第 i 个结点。因此，对于单链表结构而言，其数据元素读取的<strong>时间复杂度</strong>为O(n)</p>
<font color='red'>注：你需要从第一个开始一个一个去找，而不是通过下标一下子找到，所以时间复杂度为O(n)</font>

<p>（2）插入删除</p>
<p>对其任意一个位置进行增删操作，其<strong>时间复杂度</strong>为O(n)</p>
<font color='red'>注：之所以还为O(n)主要原因是你需要找到所需插入的元素</font>

<h3 id="链式表与顺序表的优缺点"><a href="#链式表与顺序表的优缺点" class="headerlink" title="链式表与顺序表的优缺点"></a>链式表与顺序表的优缺点</h3><h4 id="缺点"><a href="#缺点" class="headerlink" title="缺点"></a>缺点</h4><p>链式表存取操作的时间复杂度更高</p>
<h4 id="优点"><a href="#优点" class="headerlink" title="优点"></a>优点</h4><p>虽然插入删除两种时间复杂度都为都为O(n)，但是如果需要插入删除，顺序表由于每次插入删除都要移动其他元素，所以每次都为O(n)，而链式表第一次插入时查找到所需要的位置，之后的插入删除操作仅需要修改一下指针，所以之后的插入删除操作的时间复杂度为O(1)</p>
<h3 id="链式表与顺序表的选择"><a href="#链式表与顺序表的选择" class="headerlink" title="链式表与顺序表的选择"></a>链式表与顺序表的选择</h3><p>经常进行存取操作时，可选择顺序表</p>
<p>经常进行插删操作时，可选择链式表</p>
<h3 id="循环链表"><a href="#循环链表" class="headerlink" title="循环链表"></a>循环链表</h3><h4 id="定义-3"><a href="#定义-3" class="headerlink" title="定义"></a>定义</h4><p>将单链表中的<strong>终端结点</strong>的<strong>指针端</strong>由<strong>空指针改为指向头结点</strong>就使整个单链表<strong>形成一个环</strong>这种头尾相接的单链表称为单循环链表，简称 <strong>循环链表</strong></p>
<font color='red'>个人翻译：就是把链表最后的结点的下一个结点指向第一个结点</font>

<font color='orange'>注：头结点的作用是判断首尾，并非每一个循环链表都需要头结点</font>

<h4 id="作用"><a href="#作用" class="headerlink" title="作用"></a>作用</h4><p>循环链表要好使用需要设置一个尾指针指向循环链表的最后一个结点，这样便可以使<strong>寻找尾结点</strong>的时间复杂度调为O(1),并且<strong>寻找头结点</strong>也只需要<strong>移动到下一个或下下个结点</strong>，时间复杂度也为O(1)</p>
<h3 id="双向链表"><a href="#双向链表" class="headerlink" title="双向链表"></a>双向链表</h3><h4 id="定义-4"><a href="#定义-4" class="headerlink" title="定义"></a>定义</h4><p>在<strong>单链表</strong>的<strong>每个结点中</strong>，<strong>再设置一个指向其前驱结点的指针域</strong></p>
<h4 id="双向循环链表"><a href="#双向循环链表" class="headerlink" title="双向循环链表"></a>双向循环链表</h4><p>既然单链表有循环链表，那双向链表自然有双向循环链表</p>
<h5 id="双向循环链表重点"><a href="#双向循环链表重点" class="headerlink" title="双向循环链表重点"></a>双向循环链表重点</h5><p>双向循环链表最重要的是在插入删除时的操作顺序</p>
<p>插入时：</p>
<p><img src="https://s2.loli.net/2022/01/10/syzpeZQOdlaIYRg.jpg" alt=""></p>
<p>删除时：</p>
<p><img src="https://s2.loli.net/2022/01/10/jdohleCOLcy4VTD.jpg" alt=""></p>
<font color='red'>删除时记得要将删除的结点释放</font>





<h2 id="第四章：栈与队列"><a href="#第四章：栈与队列" class="headerlink" title="第四章：栈与队列"></a>第四章：栈与队列</h2><h3 id="栈"><a href="#栈" class="headerlink" title="栈"></a>栈</h3><h4 id="定义-5"><a href="#定义-5" class="headerlink" title="定义"></a>定义</h4><p>栈是限定仅在表尾进行插入和删除操作的线性表</p>
<font color='red'>个人翻译：看过弹夹吗，他只会在装弹口进行装弹和弹出操作，这就是栈</font>

<p><strong>允许</strong>插入删除操作的一端为<strong>栈顶</strong>，另一端为<strong>栈底</strong></p>
<p>栈的<strong>插入操作</strong>称为<strong>入栈</strong></p>
<p>栈的<strong>删除操作</strong>称为<strong>出栈</strong></p>
<p><strong>不含任何任何数据元素</strong>的栈称为 <strong>空栈</strong></p>
<h4 id="特性-2"><a href="#特性-2" class="headerlink" title="特性"></a>特性</h4><p>栈最显著的特性就是<strong><font color='red'>先进后出</font></strong></p>
<h4 id="栈的分类"><a href="#栈的分类" class="headerlink" title="栈的分类"></a>栈的分类</h4><h5 id="顺序栈"><a href="#顺序栈" class="headerlink" title="顺序栈"></a>顺序栈</h5><p>可以使用<strong>线性表的顺序存储结构（即数组）</strong>实现栈，<strong>将之称之为顺序栈</strong></p>
<p>所有<strong><font color='cornflowerblue'>顺序存储的结构</font></strong>都有一个很致命的<strong>问题</strong>就是需要事先确定一个<strong><font color='cornflowerblue'>固定的长度</font></strong>，固定长度所导致的问题就是<strong><font color='cornflowerblue'>内存空间的浪费</font></strong>或是<strong><font color='cornflowerblue'>内存的溢出</font></strong></p>
<p>同样的他们也都有一个<strong>优势</strong>就是<strong>存取定位</strong>非常<strong>方便</strong></p>
<h5 id="链式栈"><a href="#链式栈" class="headerlink" title="链式栈"></a>链式栈</h5><p>可以使用<strong>单链表</strong>实现栈，<strong>称之为链式栈</strong></p>
<p>所有<strong><font color='cornflowerblue'>链式存储的结构</font></strong>也都有一个很致命的<strong>问题</strong>就是在每一个数据结点中都需要增加一个指针域，这会<strong><font color='cornflowerblue'>增加内存的开销</font></strong>，但好处是<strong><font color='cornflowerblue'>栈的长度一般来说是无限的</font></strong></p>
<h4 id="时间复杂度-2"><a href="#时间复杂度-2" class="headerlink" title="时间复杂度"></a>时间复杂度</h4><p>由于插入操作皆是在队尾进行，所以当有一个指针一直指在队尾时无论是顺序表还是链式表时间复杂度都为O(1)</p>
<h4 id="栈的应用"><a href="#栈的应用" class="headerlink" title="栈的应用"></a>栈的应用</h4><h5 id="四则运算"><a href="#四则运算" class="headerlink" title="四则运算"></a>四则运算</h5><p>方法：</p>
<p>一、首先通过栈将中缀表达式转化为后缀表达式</p>
<p>规则：</p>
<ol>
<li><p>数字直接加入后缀表达式</p>
</li>
<li><p>如果是‘(’, 入栈</p>
</li>
<li><p>如果是‘)’, 则依次把栈中的运算符加入后缀表达式，直到出现‘(’并从栈中删除它</p>
</li>
<li><p>如果是运算符 + - * /</p>
<p>a.栈空或者栈顶元素为‘(’, 入栈</p>
<p>b.高于栈顶元素优先级，入栈</p>
<p>c.否则依次弹出栈顶运算符，直到遇到一个优先级小于它的运算符或者是遇到‘(’为止</p>
</li>
<li><p>遍历完成后，如果栈非空则依次弹出所有栈顶元素加入到表达式当中</p>
</li>
</ol>
<p>二、通过栈得到运算结果</p>
<p>从左到右,遇到运算符就弹出相应的运算数,运算后再把结果入栈.最终结果就是栈顶数的值.</p>
<h3 id="队列"><a href="#队列" class="headerlink" title="队列"></a>队列</h3><h4 id="定义-6"><a href="#定义-6" class="headerlink" title="定义"></a>定义</h4><p>队列是允许在<strong><font color='red'>一端进行插入操作</font></strong>，而在<strong><font color='red'>另一端进行删除操作</font></strong>的线性表。</p>
<p>允许<strong><font color='red'>删除</font></strong>的一端称为<strong><font color='red'>队头</font></strong></p>
<p>允许<strong><font color='red'>插入</font></strong>的一端称为<strong><font color='red'>队尾</font></strong></p>
<h4 id="特性-3"><a href="#特性-3" class="headerlink" title="特性"></a>特性</h4><p>队列是先进先出</p>
<h4 id="队列分类"><a href="#队列分类" class="headerlink" title="队列分类"></a>队列分类</h4><p>顺序队列</p>
<p>链式队列</p>
<h4 id="循环队列"><a href="#循环队列" class="headerlink" title="循环队列"></a>循环队列</h4><p>顺序队列会造成一个问题，就是假溢出，队头元素出栈后，并不能像顺序表一样，将剩下的元素集体往前面移一个地址，就会造成，队列前面明明有大量的空间未被使用但是元素排到队尾造成假溢出，为了解决这个问题就引入了循环链表的概念。</p>
<h5 id="定义-7"><a href="#定义-7" class="headerlink" title="定义"></a>定义</h5><p>将头尾相接的顺序存储结构称为循环队列</p>
<p>当头尾相接时虽然解决了假溢出的问题，但是同样也产生了一个问题，无法判断队列是否已满。</p>
<h5 id="判断队列是否已满的方法"><a href="#判断队列是否已满的方法" class="headerlink" title="判断队列是否已满的方法"></a>判断队列是否已满的方法</h5><h6 id="第一种"><a href="#第一种" class="headerlink" title="第一种"></a>第一种</h6><p>设置一个标志变量，当front==rear，且flag=0时为队列空</p>
<p>当front==rear，且flag=1时为队列满</p>
<h6 id="第二种"><a href="#第二种" class="headerlink" title="第二种"></a>第二种</h6><p>当队列空时，front==rear，当队列满时，我们修改它的条件，保留一个元素空间。也就是说，队列满是，数组中还有一个空闲单元。</p>
<p>所以循环队列求队伍长度（rear-front+maxsize）%maxsize通过这个公式也可判定队列是否满了</p>
<h2 id="第五章：串"><a href="#第五章：串" class="headerlink" title="第五章：串"></a>第五章：串</h2><h3 id="定义-8"><a href="#定义-8" class="headerlink" title="定义"></a>定义</h3><p>串是由<strong><font color='red'>零个或多个字符</font></strong>组成的<strong>有限序列</strong>，又名<strong><font color='red'>字符串</font></strong></p>
<p>串中的字符数目称为串的长度</p>
<p><strong>零个字符</strong>的串称为<strong><font color='red'>空串</font></strong></p>
<h3 id="分类"><a href="#分类" class="headerlink" title="分类"></a>分类</h3><p>串与线性表很像，只是限定了串中的元素必须为字符</p>
<p>故字符串的分类与线性表是一样的</p>
<p>串分为<strong>顺序存储结构</strong>以及<strong>链式存储结构</strong></p>
<p><strong><font color='red'>注：这章有个模式匹配算法，比较复杂，有机会的话再总结成一篇</font></strong></p>
<h2 id="第六章：树"><a href="#第六章：树" class="headerlink" title="第六章：树"></a>第六章：树</h2><h3 id="定义-9"><a href="#定义-9" class="headerlink" title="定义"></a>定义</h3><p>树是n个结点的有限集</p>
<p>n=0时称为空树</p>
<p><strong><font color='red'>注：个人感觉这个定义啥也没说，所以要判断一个东西是不是树，应该用下面的特点进行判断</font></strong></p>
<h3 id="特点"><a href="#特点" class="headerlink" title="特点"></a>特点</h3><p><strong><font color='red'>有且仅有一个</font></strong>特定的称为<strong><font color='red'>根</font></strong>的结点</p>
<p>当n&gt;1时，其余结点可<strong>分为</strong>m（m&gt;0）个 <strong>互不相交的有限集</strong>，其中的<strong>每一个集合</strong>本身又是一颗<strong>树</strong>，并且称为根的子树</p>
<h3 id="基本术语"><a href="#基本术语" class="headerlink" title="基本术语"></a>基本术语</h3><p><strong><font color='red'>结点</font></strong>拥有的<strong><font color='red'>子树数</font></strong>称为结点的<strong><font color='red'>度</font></strong></p>
<p><strong>度为0</strong>的结点称为<strong>叶节点</strong>或<strong>终端结点</strong></p>
<p><strong><font color='red'>个人翻译：该结点下面没有其他结点了，这个结点就是终端结点</font></strong></p>
<p>度不为0的结点就是非终端节点或分支节点</p>
<p>除根节点以外的分支结点称为内部结点</p>
<p>树的度就是内部结点中度的最大值</p>
<h4 id="结点之间的关系"><a href="#结点之间的关系" class="headerlink" title="结点之间的关系"></a>结点之间的关系</h4><p>结点的子树的根称为该结点的孩子，该节点称为孩子的双亲。</p>
<p><strong><font color='red'>个人翻译：与某个结点相连的结点中，在这个结点上面的就是该结点的双亲，在这个结点下面的就是这个结点的孩子</font></strong></p>
<p><strong>同一个双亲</strong>的孩子互相之间互称兄弟</p>
<p>结点的祖先是从根到该节点所经分支上的所有节点</p>
<p>以某节点为根的子树中的任一结点都称为该节点的子孙</p>
<h4 id="树的层次"><a href="#树的层次" class="headerlink" title="树的层次"></a>树的层次</h4><p><img src="https://s2.loli.net/2022/06/20/6jpkPCs1vG549Ni.png" alt=""></p>
<h4 id="有序树"><a href="#有序树" class="headerlink" title="有序树"></a>有序树</h4><p>如果将树中的结点的<strong>各子树看成从左至右是有次序</strong>的，不能互换的，则称该树为<strong>有序树</strong>，否则称为<strong>无序树</strong></p>
<h4 id="森林"><a href="#森林" class="headerlink" title="森林"></a>森林</h4><p>森林时m颗互不相交的树的集合</p>
<h3 id="二叉树（重点）"><a href="#二叉树（重点）" class="headerlink" title="二叉树（重点）"></a><strong><font color='red'>二叉树</font></strong>（重点）</h3><h4 id="定义-10"><a href="#定义-10" class="headerlink" title="定义"></a>定义</h4><p>二叉树是n个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两颗互不相交的，分别称为根结点的左子树和右子树的二叉树组成</p>
<p><strong><font color='red'>个人翻译：除了空集这个比较特殊的二叉树，如果看到一颗树它的所有结点的子节点最多只有两个，那这个树就是二叉树</font></strong></p>
<h4 id="特点-1"><a href="#特点-1" class="headerlink" title="特点"></a>特点</h4><ol>
<li>每个结点<strong>最多</strong>只能有两棵<strong>子树</strong></li>
<li>左子树和右子树是<strong>有顺序的</strong>，次序不能任意颠倒</li>
<li>即使树中某结点只有一棵子树，也要区分它是左子树还是右子树</li>
</ol>
<h4 id="特殊二叉树"><a href="#特殊二叉树" class="headerlink" title="特殊二叉树"></a>特殊二叉树</h4><h5 id="满二叉树"><a href="#满二叉树" class="headerlink" title="满二叉树"></a>满二叉树</h5><p>定义：只含度为0和2的结点且度为0的结点只出现在最后一层的二叉树称为满二叉树</p>
<h5 id="完全二叉树"><a href="#完全二叉树" class="headerlink" title="完全二叉树"></a>完全二叉树</h5><p>定义：对任意一颗满二叉树，从它的最后一层的最右结点起，按从下到上、从右到左的次序去掉若干个结点后所得到的二叉树称为完全二叉树</p>
<h4 id="特性-4"><a href="#特性-4" class="headerlink" title="特性"></a>特性</h4><p>1.在二叉树的第i层上至多有$2^{i-1}$个结点</p>
<p>2.深度为k的二叉树至多有$2^k-1$个结点</p>
<p>3.对任何一颗二叉树T，如果其<strong>叶子结点点数</strong>为$n_0$，<strong>度（</strong>即子结点数)<strong>为 2</strong> 的<strong>结点数</strong>为$n_1$，则$n_0=n_1+1$</p>
<p>4.具有n个结点的<font color='lime'>**完全二叉树</font>**的深度$[log2n]+1$</p>
<font color='red'>注：</font><font color='red'>$[x]$表示不大于x的最大整数</font>

<p>5.如果对一棵树有n个结点的<strong>完全二叉树</strong>（其<strong>深度</strong>为$[log2n]+1$的结点按层次编号，从左到右，对任一结点i有</p>
<p>a.如果i=1，则该结点为根结点，无双亲，若i&gt;1，则其双亲为i/2</p>
<p>b.如果2i&gt;n，则节点i无左孩子（结点i为叶子节点），否则其左孩子为2i</p>
<p>c.如果结点2i+1&gt;n，则节点i无右孩子，否则其右结点为2i+1</p>
<h4 id="二叉树的遍历"><a href="#二叉树的遍历" class="headerlink" title="二叉树的遍历"></a>二叉树的遍历</h4><p>二叉树遍历均有两种比较实用的算法：一种为递归算法，一种则是非递归的算法</p>
<h5 id="先序遍历"><a href="#先序遍历" class="headerlink" title="先序遍历"></a>先序遍历</h5><p>如果二叉树为空，则进行空操作，否则进行以下操作：</p>
<p>1.访问根节点</p>
<p>2.先序遍历左子树</p>
<p>3.先序遍历右子树</p>
<p>递归算法：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="type">void</span> <span class="title">PreOrderTraversal</span><span class="params">(BinTree *BT)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(BT)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot;%d&quot;</span>,BT-&gt;Data);</span><br><span class="line">		<span class="built_in">PreOrderTraversal</span>(BT-&gt;Left);</span><br><span class="line">		<span class="built_in">PreOrderTraversal</span>(BT-&gt;Right);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<p>思路：运用递归的思想，如果左子树不为空就一直访问左子树，直到左子树为空，左子树为空则会回到上一次递归，访问右子树，以右子树为根结点继续优先访问左子树，直到左子树为空，又跳出本次递归，然后一层一层的解递归，就能最终将整颗二叉树访问完毕。</p>
<p>非递归算法：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="type">void</span> <span class="title">PreOrderTraversal</span><span class="params">(BinTree *BT)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="keyword">if</span> (!BT)</span><br><span class="line">		<span class="keyword">return</span>;</span><br><span class="line">	BinTree *P = BT;</span><br><span class="line">	stack&lt;BinTree*&gt;st;</span><br><span class="line">	<span class="keyword">while</span> (P != <span class="literal">NULL</span> || !st.<span class="built_in">empty</span>())</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">while</span> (P)</span><br><span class="line">		&#123;</span><br><span class="line">			st.<span class="built_in">push</span>(P);</span><br><span class="line">			cout &lt;&lt; P-&gt;Value &lt;&lt; endl;</span><br><span class="line">			P = P-&gt;Left;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span> (!st.<span class="built_in">empty</span>())</span><br><span class="line">		&#123;</span><br><span class="line">			P = st.<span class="built_in">top</span>();</span><br><span class="line">			st.<span class="built_in">pop</span>();</span><br><span class="line">			P = P-&gt;Right;</span><br><span class="line">		&#125;</span><br><span class="line"></span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<p>思路：非递归算法需要用到之前所学到的线性表的栈，整体思路则是将根结点放入栈中，访问左节点，将左节点放入栈中，只要左节点不为空则一直访问左节点，并将它放入栈中，当左节点为空则访问这个节点的右结点，并将该节点放入栈中，然后继续访问右结点的左节点，然后将右结点放入栈中，直到访问到叶子节点，则取出栈头元素，访问其右结点</p>
<h5 id="中序遍历"><a href="#中序遍历" class="headerlink" title="中序遍历"></a>中序遍历</h5><p>1.中序遍历所有左子树</p>
<p>2.访问根节点</p>
<p>3.中序遍历所有右子树</p>
<p>两种算法思路与先序遍历基本一致，此处不再赘述，只提供相应代码</p>
<p>递归算法：</p>
<figure class="highlight cc"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="type">void</span> <span class="title">PreOrderTraversal</span><span class="params">(BinTree *BT)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(BT)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="built_in">PreOrderTraversal</span>(BT-&gt;Left);</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot;%d&quot;</span>,BT-&gt;Data);</span><br><span class="line">		<span class="built_in">PreOrderTraversal</span>(BT-&gt;Right);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<p>非递归算法：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="type">void</span> <span class="title">PreOrderTraversal</span><span class="params">(BinTree *BT)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="keyword">if</span> (!BT)</span><br><span class="line">		<span class="keyword">return</span>;</span><br><span class="line">	BinTree *P = BT;</span><br><span class="line">	stack&lt;BinTree*&gt;st;</span><br><span class="line">	<span class="keyword">while</span> (P != <span class="literal">NULL</span> || !st.<span class="built_in">empty</span>())</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">while</span> (P)<span class="comment">//一直向左并将沿途节点压入栈</span></span><br><span class="line">		&#123;</span><br><span class="line">			st.<span class="built_in">push</span>(P);</span><br><span class="line">			P = P-&gt;Left;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span> (!st.<span class="built_in">empty</span>())</span><br><span class="line">		&#123;</span><br><span class="line">			P = st.<span class="built_in">top</span>();</span><br><span class="line">			cout &lt;&lt; P-&gt;Value &lt;&lt; endl; </span><br><span class="line">			st.<span class="built_in">pop</span>();</span><br><span class="line">			P = P-&gt;Right;<span class="comment">//向右访问右子树</span></span><br><span class="line">		&#125;</span><br><span class="line"></span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<h5 id="后序遍历"><a href="#后序遍历" class="headerlink" title="后序遍历"></a>后序遍历</h5><p>1.后序遍历左节点</p>
<p>2.后序遍历右结点</p>
<p>3.访问根节点</p>
<p>递归算法：</p>
<figure class="highlight cc"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="type">void</span> <span class="title">PreOrderTraversal</span><span class="params">(BinTree *BT)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(BT)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="built_in">PreOrderTraversal</span>(BT-&gt;Left);</span><br><span class="line">		<span class="built_in">PreOrderTraversal</span>(BT-&gt;Right);</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot;%d&quot;</span>,BT-&gt;Data);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<p>非递归算法：</p>
<figure class="highlight cc"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="type">void</span> <span class="title">PreOrderTraversal</span><span class="params">(BinTree *BT)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="keyword">if</span> (!BT)</span><br><span class="line">		<span class="keyword">return</span>;</span><br><span class="line">	BinTree *P = BT，*Flag = <span class="literal">NULL</span>;</span><br><span class="line">	stack&lt;BinTree*&gt;st;</span><br><span class="line">	<span class="keyword">while</span> (P != <span class="literal">NULL</span> || !st.<span class="built_in">empty</span>())</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">if</span>(P)<span class="comment">//走到最左边</span></span><br><span class="line">		&#123;</span><br><span class="line">			st.<span class="built_in">push</span>(P);</span><br><span class="line">			P = P-&gt;Left;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">else</span></span><br><span class="line">		&#123;</span><br><span class="line">			P = st.<span class="built_in">top</span>();</span><br><span class="line">			<span class="keyword">if</span>(P-&gt;Right != <span class="literal">NULL</span> &amp;&amp; P-&gt;Right != Flag)<span class="comment">//右子树存在，并且未被访问</span></span><br><span class="line">			&#123;</span><br><span class="line">				P = P-&gt;Right;</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">else</span></span><br><span class="line">			&#123;</span><br><span class="line">				st.<span class="built_in">pop</span>();</span><br><span class="line">				cout &lt;&lt; P-&gt;value &lt;&lt; endl;</span><br><span class="line">				Flag = P;</span><br><span class="line">				P = <span class="literal">NULL</span>;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line"></span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<h5 id="层次遍历"><a href="#层次遍历" class="headerlink" title="层次遍历"></a>层次遍历</h5><p>二叉树的层次遍历就是按照二叉树的层次，从上到下，从左到右依次遍历，为了实现这种遍历方式则需要用到之前所学到的队列</p>
<figure class="highlight cc"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="type">void</span> <span class="title">travLevel</span> <span class="params">( BinTreeNode&lt;T&gt;* root )</span> </span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">   Queue&lt;BinTreeNode&lt;T&gt;*&gt; Q;</span><br><span class="line">   Q.<span class="built_in">enqueue</span> ( root ); <span class="comment">//根节点入队</span></span><br><span class="line">   <span class="keyword">while</span> ( !Q.<span class="built_in">empty</span>() ) </span><br><span class="line">   &#123; </span><br><span class="line">      BinTreeNode&lt;T&gt;* x = Q.<span class="built_in">dequeue</span>(); cout &lt;&lt; x-&gt;data; <span class="comment">//取出队首节点并访问之</span></span><br><span class="line">      <span class="keyword">if</span> ( x-&gt;LeftChild ) Q.<span class="built_in">enqueue</span> ( x-&gt;LeftChild ); <span class="comment">//左孩子入队</span></span><br><span class="line">      <span class="keyword">if</span> ( x-&gt;RightChild ) Q.<span class="built_in">enqueue</span> ( x-&gt;RightChild ); <span class="comment">//右孩子入队</span></span><br><span class="line">   &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<p>思路：首先将根节点放入队列，然后出队，访问根节点，将根节点的左孩子右孩子依次放入队列中，再依次从队列中取出各个结点，重复刚才的操作，直到队列为空。</p>
<h4 id="线索二叉树"><a href="#线索二叉树" class="headerlink" title="线索二叉树"></a>线索二叉树</h4><p>由于二叉树中有些节点或是左节点为空，或是右结点为空，或是都为空，会导致二叉树对内存的浪费，于是提出了线索二叉树的概念。</p>
<h5 id="定义-11"><a href="#定义-11" class="headerlink" title="定义"></a>定义</h5><p>利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。</p>
<p>事实上如果只是为了应付考试，只需要知道线索二叉树怎么画就行了</p>
<h5 id="线索二叉树的画法"><a href="#线索二叉树的画法" class="headerlink" title="线索二叉树的画法"></a>线索二叉树的画法</h5><h6 id="重要规则"><a href="#重要规则" class="headerlink" title="重要规则"></a>重要规则</h6><p>如果一个结点的左孩子为空，则指向它的前驱结点。</p>
<p>如果一个结点右孩子为空，则指向它的后继。</p>
<p>举个例子</p>
<p><img src="https://s2.loli.net/2022/10/19/Y8CAuiJp4axBZW1.png" alt=""></p>
<p>假设要画这个二叉树的中序二叉树</p>
<p>先写出它中序遍历的结果：DFBACE</p>
<p>然后画出每个结点的结构<img src="https://s2.loli.net/2022/10/19/fSTzdZxqMFkyD2p.png" alt=""></p>
<p><strong><font color='red'>注：结点名字左右两边的数字作为标志，该节点如果有左孩子，左标志为0，否则为1，右孩子亦然</font></strong></p>
<p>接下来通过重要规则以及中序遍历结果连线就完事了</p>
<p><img src="https://s2.loli.net/2022/10/19/o9fIQeOcGyCHWu2.png" alt=""></p>
<h4 id="树，森林，二叉树转换"><a href="#树，森林，二叉树转换" class="headerlink" title="树，森林，二叉树转换"></a>树，森林，二叉树转换</h4><p>我自己是看的这篇文章，写的真不错啊（主要我懒得画图）</p>
<p><a target="_blank" rel="noopener" href="https://blog.csdn.net/leolinsheng/article/details/11745559">https://blog.csdn.net/leolinsheng/article/details/11745559</a></p>
<h4 id="哈夫曼树以及哈夫曼编码"><a href="#哈夫曼树以及哈夫曼编码" class="headerlink" title="哈夫曼树以及哈夫曼编码"></a>哈夫曼树以及哈夫曼编码</h4><p>这位大佬通过举例子的方式讲的哈夫曼树以及哈夫曼编码，仔细看很容易看懂（懒得画图，开摆了）</p>
<p><a target="_blank" rel="noopener" href="https://www.cnblogs.com/kubixuesheng/p/4397798.html">https://www.cnblogs.com/kubixuesheng/p/4397798.html</a></p>
<h2 id="第七章：图"><a href="#第七章：图" class="headerlink" title="第七章：图"></a>第七章：图</h2><h3 id="定义-12"><a href="#定义-12" class="headerlink" title="定义"></a>定义</h3><p>由<font color='red'>顶点的</font>有穷非空<font color='red'>集合</font>和顶点之间的<font color='red'>边的集合</font>组成。</p>
<p><strong><font color='red'>个人翻译:点之间连着线就是图</font></strong></p>
<h3 id="数据结构间的区别"><a href="#数据结构间的区别" class="headerlink" title="数据结构间的区别"></a>数据结构间的区别</h3><p>线性表：一对一，只有前驱和后驱</p>
<p>树：一对多，一个结点对应多个子节点，一个根节点</p>
<p>图：多对多，多个顶点对应多个顶点</p>
<h3 id="图的分类"><a href="#图的分类" class="headerlink" title="图的分类"></a>图的分类</h3><h4 id="无向图"><a href="#无向图" class="headerlink" title="无向图"></a>无向图</h4><p>若顶点$v_i$到$v_j$之间的<font color='red'>边没有方向</font>，那么这条边就是<font color='red'>无向边</font></p>
<p>如果图中任意两个结点之间的边都是无向边，则称为无向图</p>
<p>无向图<font color='red'>顶点的边数</font>叫做<font color='red'>顶点的度</font></p>
<h4 id="有向图"><a href="#有向图" class="headerlink" title="有向图"></a>有向图</h4><p>若从顶点$v_i$到$v_j$的边有方向，则称这条边为有向边，也称为弧</p>
<p>如果图中任意两个顶点之间的边都是有向边，则称该图为 有向图</p>
<font color='red'>指向自己的边的条数</font>称为顶点的<font color='red'>入度</font>，<font color='red'>由自己指出去的边的条数</font>称为<font color='red'>出度</font>

<h4 id="简单图"><a href="#简单图" class="headerlink" title="简单图"></a>简单图</h4><p>在图中，若<strong>不存在</strong>顶点到其自身的边<strong>，且</strong>同一条边不重复出现，则称这样的图为简单图</p>
<h4 id="无向完全图"><a href="#无向完全图" class="headerlink" title="无向完全图"></a>无向完全图</h4><p>在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图</p>
<h4 id="有向完全图"><a href="#有向完全图" class="headerlink" title="有向完全图"></a>有向完全图</h4><p>在有向图中，如果任意两个顶点之间都存在 方向互为相反 的两条弧，则称该图为有向完全图</p>
<h3 id="权"><a href="#权" class="headerlink" title="权"></a>权</h3><p>有些图的边或弧具有相应的权值，这种与图的边有关的数被称为权</p>
<font color='red'>带权的图</font>一般被称之为<font color='red'>网</font>



<font color='red'>个人翻译：好比两个点之间有路，路就是图的边，而距离就是这条边的权</font>

<h3 id="连通图"><a href="#连通图" class="headerlink" title="连通图"></a>连通图</h3><p>图中顶点间存在路径，两顶点存在路径则说明是<font color='red'>连通</font>的</p>
<p>没有重复顶点的路径称为简单路径</p>
<h5 id="无向"><a href="#无向" class="headerlink" title="无向"></a>无向</h5><p>如果无向图中任意两个结点是连通的，则称之为连通图</p>
<h5 id="有向"><a href="#有向" class="headerlink" title="有向"></a>有向</h5><p>有向连通图分为弱连通，单向连通，强连通</p>
<p>弱连通：有向图的底图（无向图）是连通图，则是弱连通图</p>
<p>单向连通：有向图中，任意两个结点至少有一个到另一个是可达的，则是单向连通图</p>
<p>强连通：有向图中，任意两个结点互相可达，则该图为强连通图</p>
<h3 id="图的存储结构"><a href="#图的存储结构" class="headerlink" title="图的存储结构"></a>图的存储结构</h3><p>计算机只认识01，所以我们不可能在cpu上面画一个图然后逼着cpu完成运算</p>
<p>于是便有了图的存储结构，和线性表一样，图的存储结构也分为两种分别是：邻接矩阵，邻接表</p>
<h4 id="邻接矩阵"><a href="#邻接矩阵" class="headerlink" title="邻接矩阵"></a>邻接矩阵</h4><p>图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。</p>
<h4 id="邻接表"><a href="#邻接表" class="headerlink" title="邻接表"></a>邻接表</h4><p>用单链表和顺序存储的方式来存放图</p>
<p>这个存储结构比较复杂，我觉得我会讲错，所以摆烂了，想要学习的可以去看看这位大佬的</p>
<p><a target="_blank" rel="noopener" href="https://blog.csdn.net/m0_46518461/article/details/109547298">https://blog.csdn.net/m0_46518461/article/details/109547298</a></p>
<h3 id="图的遍历"><a href="#图的遍历" class="headerlink" title="图的遍历"></a>图的遍历</h3><p>图的遍历也是有两种方法，分别是深度优先遍历，广度优先遍历</p>
<h4 id="深度优先遍历"><a href="#深度优先遍历" class="headerlink" title="深度优先遍历"></a>深度优先遍历</h4><p>由名字可得优先向前访问</p>
<p>首先以一个未被访问过的顶点作为起始顶点沿当前顶点的边走到未访问过的顶点</p>
<p>当没有未访问过的顶点时则回到上一个顶点继续试探别的顶点，直至所有的顶点都被访问过</p>
<h4 id="广度优先遍历"><a href="#广度优先遍历" class="headerlink" title="广度优先遍历"></a>广度优先遍历</h4><p>同样由名字可得优先对一个结点指向的其他所有未被访问的结点进行遍历</p>
<p>依次将访问到的顶点放入队列，然后依次访问他们的下一个结点，访问到的均放入队列</p>
<p>直到队列为空，整个图访问结束</p>
<font color='red'>可以用来解最短路径问题</font>

<h3 id="最小生成树"><a href="#最小生成树" class="headerlink" title="最小生成树"></a>最小生成树</h3><p>最小生成树包含两种算法，分别是普利姆算法和克鲁斯卡尔算法，由于我实在懒的画图所以也粘一篇大佬的文章了</p>
<p><a target="_blank" rel="noopener" href="https://blog.csdn.net/liu17234050/article/details/104262387">https://blog.csdn.net/liu17234050/article/details/104262387</a></p>
<h3 id="拓扑排序"><a href="#拓扑排序" class="headerlink" title="拓扑排序"></a>拓扑排序</h3><p>这个很简单，只要按着以下步骤走就没问题</p>
<p>1.寻找未被指向的结点，将他取出（若有多个选其一）</p>
<p>2.去除取出的结点和与它相连的线</p>
<p>3.执行第一步</p>
<p>4.直到整个图都完成排序</p>
</div>
        </div>
        
            <div class="kratos-copyright text-center clearfix">
                <h5 itemprop="copyrightNotice">本作品采用 <a rel="license nofollow" target="_blank" href="https://creativecommons.org/licenses/by-sa/4.0/">知识共享署名-相同方式共享 4.0 国际许可协议</a> 进行许可</h5>
            </div>
        
        <footer class="kratos-entry-footer clearfix">
            
                <div class="post-like-donate text-center clearfix" id="post-like-donate">
                
                
                    <a class="share" href="javascript:;"><i class="fa fa-share-alt"></i> 分享</a>
                    <div class="share-wrap" style="display: none;">
    <div class="share-group">
        <a href="javascript:;" class="share-plain qq" onclick="share('qq');" rel="nofollow">
            <div class="icon-wrap">
                <i class="fa fa-qq"></i>
            </div>
        </a>
        <a href="javascript:;" class="share-plain qzone" onclick="share('qzone');" rel="nofollow">
            <div class="icon-wrap">
                <i class="fa fa-star"></i>
            </div>
        </a>
        <a href="javascript:;" class="share-plain weixin pop style-plain" rel="nofollow">
            <div class="icon-wrap">
                <i class="fa fa-weixin"></i>
            </div>
            <div class="share-int">
                <div class="qrcode" id="wechat-qr"></div>
                <p>打开微信“扫一扫”，打开网页后点击屏幕右上角分享按钮</p>
            </div>
        </a>
        <a href="javascript:;" class="share-plain weibo" onclick="share('weibo');" rel="nofollow">
            <div class="icon-wrap">
                <i class="fa fa-weibo"></i>
            </div>
        </a>
        <a href="javascript:;" class="share-plain facebook style-plain" onclick="share('facebook');" rel="nofollow">
            <div class="icon-wrap">
                <i class="fa fa-facebook"></i>
            </div>
        </a>
        <a href="javascript:;" class="share-plain twitter style-plain" onclick="share('twitter');" rel="nofollow">
            <div class="icon-wrap">
                <i class="fa fa-twitter"></i>
            </div>
        </a>
    </div>
    <script type="text/javascript">
        $(()=>{
            new QRCode("wechat-qr", {
                text: "http://example.com/2022/12/25/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AC%94%E8%AE%B0/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AC%94%E8%AE%B0/",
                width: 150,
                height: 150,
                correctLevel : QRCode.CorrectLevel.H
            });
        });
        function share(dest) {
            const qqBase        = "https://connect.qq.com/widget/shareqq/index.html?";
            const weiboBase     = "https://service.weibo.com/share/share.php?";
            const qzoneBase     = "https://sns.qzone.qq.com/cgi-bin/qzshare/cgi_qzshare_onekey?";
            const facebookBase  = "https://www.facebook.com/sharer/sharer.php?";
            const twitterBase   = "https://twitter.com/intent/tweet?";
            const hostUrl       = "http://example.com/2022/12/25/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AC%94%E8%AE%B0/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AC%94%E8%AE%B0/";
            const title         = "「数据结构笔记」";
            const excerpt       = `本笔记是我大一的时候自学数据结构所总结的笔记。内容不多，深度也比较低，想对数据结构进行精进的大可不必看这个，如果只是为了应付学校的考试或者入个门，这个倒是足够了。`;
            let _URL;
            switch (dest) {
                case "qq"       : _URL = qqBase+"url="+hostUrl+"&title="+title+"&desc=&summary="+excerpt+"&site=cxpy";     break;
                case "weibo"    : _URL = weiboBase+"url="+hostUrl+"&title="+title+excerpt;                                 break;
                case "qzone"    : _URL = qzoneBase+"url="+hostUrl+"&title="+title+"&desc=&summary="+excerpt+"&site=cxpy";  break;
                case "facebook" : _URL = facebookBase+"u="+hostUrl;                                                        break;
                case "twitter"  : _URL = twitterBase+"text="+title+excerpt+"&url="+hostUrl;                                break;
            }
            window.open(_URL);
        };
    </script>
</div>
                
                </div>
            
            <div class="footer-tag clearfix">
                <div class="pull-left">
                <i class="fa fa-tags"></i>
                    <a class="tag-none-link" href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" rel="tag">数据结构</a>, <a class="tag-none-link" href="/tags/%E7%AE%97%E6%B3%95/" rel="tag">算法</a>
                </div>
                <div class="pull-date">
                    <time datetime="2022-12-25T09:44:39.422Z" itemprop="dateModified">最后编辑：2022-12-25</time>
                </div>
            </div>
        </footer>
    </div>
    
        <nav class="navigation post-navigation clearfix" role="navigation">
            
            <div class="nav-previous clearfix">
                <a title=" C#知识(9)" href="/2022/12/24/CS知识/CS知识-9/">&lt; 上一篇</a>
            </div>
            
            
            <div class="nav-next clearfix">
                <a title=" 操作系统概述（操作系统笔记1）" href="/2022/12/31/操作系统笔记/操作系统笔记-1/">下一篇 &gt;</a>
            </div>
            
        </nav>
    
    
</article>

        

            </section>

        

                
            

<section id="kratos-widget-area" class="col-md-4 hidden-xs hidden-sm">
    <!-- 文章和页面根据splitter来分割，没有的话就从头开始设置为sticky -->
    
    
                <aside id="krw-about" class="widget widget-kratos-about clearfix">
    <div class="photo-background"></div>
    <div class="photo-wrapper clearfix">
        <div class="photo-wrapper-tip text-center">
            <img class="about-photo" src="/images/avatar.webp" loading="lazy" decoding="auto" />
        </div>
    </div>
    <div class="textwidget">
        <p class="text-center"></p>
    </div>
    <div class="site-meta">
        <a class="meta-item" href="/archives/">
            <span class="title">
                文章
            </span>
            <span class="count">
                39
            </span>
        </a>
        <a class="meta-item" href="/categories/">
            <span class="title">
                分类
            </span>
            <span class="count">
                7
            </span>
        </a>
        <a class="meta-item" href="/tags/">
            <span class="title">
                标签
            </span>
            <span class="count">
                10
            </span>
        </a>
    </div>
</aside>
            
                    <div class="sticky-area">
                
                
  <aside id="krw-categories" class="widget widget-kratos-categories clearfix">
    <h4 class="widget-title"><i class="fa fa-folder"></i>分类目录</h4>
      <ul class="category-list"><li class="category-list-item"><a class="category-list-link" href="/categories/C-%E7%9F%A5%E8%AF%86/">C#知识</a><span class="category-list-count">9</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/Lua/">Lua</a><span class="category-list-count">10</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/Unity%E7%BD%91%E7%BB%9C%E6%B8%B8%E6%88%8F%E5%BC%80%E5%8F%91/">Unity网络游戏开发</a><span class="category-list-count">3</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/%E5%AE%9D%E5%8F%AF%E6%A2%A6%E5%B0%8F%E8%AF%B4/">宝可梦小说</a><span class="category-list-count">5</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F%E7%AC%94%E8%AE%B0/">操作系统笔记</a><span class="category-list-count">10</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AC%94%E8%AE%B0/">数据结构笔记</a><span class="category-list-count">1</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/%E9%9A%8F%E6%83%B3/">随想</a><span class="category-list-count">1</span></li></ul>
  </aside>


            
                
  <aside id="krw-tags" class="widget widget-kratos-tags clearfix">
    <h4 class="widget-title"><i class="fa fa-tags"></i>标签聚合</h4>
      <div class="tag-clouds">
        <a href="/tags/C/" style="font-size: 0.75em;">C#</a> <a href="/tags/Lua/" style="font-size: 0.8em;">Lua</a> <a href="/tags/unity/" style="font-size: 0.65em;">unity</a> <a href="/tags/%E5%AE%9D%E5%8F%AF%E6%A2%A6/" style="font-size: 0.7em;">宝可梦</a> <a href="/tags/%E5%BD%B1%E8%AF%84/" style="font-size: 0.6em;">影评</a> <a href="/tags/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/" style="font-size: 0.8em;">操作系统</a> <a href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" style="font-size: 0.6em;">数据结构</a> <a href="/tags/%E7%AE%97%E6%B3%95/" style="font-size: 0.6em;">算法</a> <a href="/tags/%E7%BD%91%E7%BB%9C%E6%B8%B8%E6%88%8F/" style="font-size: 0.65em;">网络游戏</a> <a href="/tags/%E9%9A%8F%E6%83%B3/" style="font-size: 0.6em;">随想</a>
      </div>
  </aside>

            
                
  <aside id="krw-posts" class="widget widget-kratos-posts">
  <h4 class="widget-title"><i class="fa fa-file"></i>最新文章</h4>
  <div class="tab-content">
      <ul class="list-group">
        
        
          
          
            <a class="list-group-item" href="/2025/10/08/%E9%9A%8F%E6%83%B3/%E3%80%8A%E6%98%9F%E4%B8%89%E5%9B%BD%E3%80%8B%E5%90%90%E6%A7%BD/"><i class="fa  fa-book"></i> 《星三国》吐槽</a>
            
          
        
          
          
            <a class="list-group-item" href="/2023/08/14/%E5%AE%9D%E5%8F%AF%E6%A2%A6%E5%B0%8F%E8%AF%B4/%E5%AE%9D%E5%8F%AF%E6%A2%A6%E5%B0%8F%E8%AF%B45/"><i class="fa  fa-book"></i> 宝可梦小说第五章</a>
            
          
        
          
          
            <a class="list-group-item" href="/2023/08/13/%E5%AE%9D%E5%8F%AF%E6%A2%A6%E5%B0%8F%E8%AF%B4/%E5%AE%9D%E5%8F%AF%E6%A2%A6%E5%B0%8F%E8%AF%B44/"><i class="fa  fa-book"></i> 宝可梦小说第四章</a>
            
          
        
          
          
            <a class="list-group-item" href="/2023/08/10/%E5%AE%9D%E5%8F%AF%E6%A2%A6%E5%B0%8F%E8%AF%B4/%E5%AE%9D%E5%8F%AF%E6%A2%A6%E5%B0%8F%E8%AF%B43/"><i class="fa  fa-book"></i> 宝可梦小说第三章</a>
            
          
        
          
          
            <a class="list-group-item" href="/2023/08/09/%E5%AE%9D%E5%8F%AF%E6%A2%A6%E5%B0%8F%E8%AF%B4/%E5%AE%9D%E5%8F%AF%E6%A2%A6%E5%B0%8F%E8%AF%B42/"><i class="fa  fa-book"></i> 宝可梦小说第二章</a>
            
          
        
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
          
            
      </ul>
  </div>
  </aside>

            
    </div>
</section>
        
        </div>
    </div>
</div>
<footer>
    <div id="footer"  >
        <div class="container">
            <div class="row">
                <div class="col-md-6 col-md-offset-3 footer-list text-center">
                    <ul class="kratos-social-icons">
                        
                        
                        
                        
                        
                        
                        
                        
                        
                    </ul>
                    <ul class="kratos-copyright">
                        <div>
                            <li>&copy; 2025 舛羽的笔记小站 版权所有.</li>
                            <li>本站已运行<span id="span_dt">Loading...</span></li>
                        </div>
                        <div>
                            <li>Theme <a href="https://github.com/Candinya/Kratos-Rebirth" target="_blank">Kratos:Rebirth</a></li>
                            <li>Site built with&nbsp;<i class="fa fa-heart throb" style="color:#d43f57"></i>&nbsp;by cy.</li>
                        </div>
                        <div>
                            <li>Powered by <a href="https://hexo.io" target="_blank" rel="nofollow">Hexo</a></li>
                            <li>Hosted on <a href="https://github.io" target="_blank">Github Pages</a></li>
                        </div>
                        <div>
                            
                            
                        </div>
                    </ul>
                </div>
            </div>
        </div>
        <div class="kr-tool text-center">
            <div class="tool">
                
                    <div class="box search-box">
                        <a href="/search/">
                            <span class="fa fa-search"></span>
                        </a>
                    </div>
                
                
                    <div class="box theme-box" id="darkmode-switch">
                        <span class="fa fa-adjust"></span>
                    </div>
                
                
            </div>
            <div class="box gotop-box">
                <span class="fa fa-chevron-up"></span>
            </div>
        </div>
    </div>
</footer>
</div>
</div>

        <script defer src="/vendors/bootstrap@3.3.4/dist/js/bootstrap.min.js"></script>
<script defer src="/vendors/nprogress@0.2.0/nprogress.js"></script>
<script>
    if (!window.kr) {
        window.kr = {};
    }
    window.kr.notMobile = (!(navigator.userAgent.match(/(phone|pad|pod|iPhone|iPod|ios|iPad|Android|Mobile|BlackBerry|IEMobile|MQQBrowser|JUC|Fennec|wOSBrowser|BrowserNG|WebOS|Symbian|Windows Phone)/i)));
    window.kr.siteRoot = "/";
</script>


    <script async src="/js/candy.min.js"></script>




    <script defer src="/vendors/@fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.js"></script>

<script defer src="/vendors/clipboard@2.0.6/dist/clipboard.min.js"></script>
<script defer src="/js/kratosr.min.js"></script>
<script defer src="/js/pjax.min.js"></script>



<!-- Extra support for third-party plguins  -->


    <script type="text/x-mathjax-config">
    MathJax.Hub.Config({
        tex2jax: {
            inlineMath: [ ["$","$"], ["\\(","\\)"] ],
            skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code'],
            processEscapes: true
        }
    });
    MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax();
        for (var i = 0; i < all.length; ++i)
            all[i].SourceElement().parentNode.className += ' has-jax';
    });
</script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-MML-AM_CHTML
"></script>
</body>
</html>